Моделирование теории графов — это процесс абстрагирования сложных связей реального мира (например, маршрутизации в интернете, переходов состояний) в математический объект $G = (V, E)$. Определяя сущности каквершины (Vertex) а отношения — какрёбра (Edge)мы можем использовать единый абстрактный тип данных (ADT) и алгоритмы для решения разнообразных задач.
Основные компоненты определения
- вершины (Vertex): также называемые узлами. Имеют «ключ» (Key) как уникальный идентификатор и могут нести «полезную нагрузку» (Payload).
- рёбра (Edge): соединяет две вершины, указывая на существование связи между ними. Может быть односторонней (ориентированный граф) или двусторонней.
- вес (Weight): числовое значение на ребре, представляющее стоимость (например, расстояние, задержка, пропускная способность).
Математическая строгость
Математически, $G = (V, E)$. Здесь $V$ — множество вершин, а $E$ — множество пар $(v, w)$, где $v, w \in V$. Такая высокая степень абстракции позволяет использовать один и тот же набор алгоритмов обхода по ширине (BFS) и глубине (DFS) для решения задач от навигации по карте до рекомендаций в социальных сетях.
Подсказка моделирования: граф пространства состояний
При решении логических головоломок (например, задачи с ведрами), каждоедопустимое состояниеявляется вершиной, а каждоедопустимое действие— это ребро. Процесс решения заключается в поиске пути от начальной вершины к целевой вершине.